package sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] keys = new int[]{81, 49, 19, 38, 97, 76, 13, 19};
        System.out.print("关键字序列：");
        System.out.println(Arrays.toString(keys));
        heapSort.heapSort(keys);
    }

    //堆排序
    public void heapSort(int[] keys) {
        // 升序排序，创建最大堆
        for (int i = keys.length / 2 - 1; i >= 0; i--)
            shift(keys, i, keys.length - 1);
        System.out.print("最大堆：");
        System.out.println(Arrays.toString(keys));
        System.out.print("堆排序（升序）：");
        //每趟将最大值交换到后面，再调整成最大堆
        for (int i = keys.length - 1; i > 0; i--) {
            swap(keys, 0, i);
            shift(keys, 0, i - 1);
            System.out.print("第" + (keys.length - i) + "趟");
            System.out.println(Arrays.toString(keys));
        }
        System.out.println(Arrays.toString(keys));
    }

    //将keys数组中以parent为根的子树调整成最小/大堆，子序列范围为parent～end，minheap表示最小堆还是最大堆
    private void shift(int[] keys, int parent, int end) {
        int child = 2 * parent + 1;                              //child是parent的左孩子
        int value = keys[parent];
        while (child <= end) {
            // 比较parent孩子大小：child、child+1，记住大的孩子
            if (child < end && keys[child] < keys[child + 1])
                child++;

            // 父亲比孩子小，则将大孩子上移
            if (value < keys[child]) {
                keys[parent] = keys[child];
                parent = child;                            //parent、child两者都向下一层
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
        keys[parent] = value;                              // 插入原parent节点值
    }

    // 交换数组i,j索引存储的值
    private void swap(int[] keys, int i, int j) {
        int temp = keys[j];
        keys[j] = keys[i];
        keys[i] = temp;
    }
}
